#include <cstdlib>
#include <cstdio>

typedef  struct TreeNode{
	// 节点数据
	char data;
	// 左右线索标识 0、左右子树 1、左右线索
	int leftTag;
	int rightTag;
	// 父节点
	struct TreeNode *parent;
	// 左节点
	struct TreeNode *leftChild;
	// 右节点
	struct TreeNode *rightChild;
}TreeNode, *Tree;

void test(Tree &tree) {
	TreeNode *root = (TreeNode *) malloc(sizeof(TreeNode));

	TreeNode *rootLeft = (TreeNode *) malloc(sizeof(TreeNode));
	TreeNode *rootRight = (TreeNode *) malloc(sizeof(TreeNode));

	TreeNode *rootLeftLeft = (TreeNode *) malloc(sizeof(TreeNode));
	TreeNode *rootLeftRight = (TreeNode *) malloc(sizeof(TreeNode));
	TreeNode *rootRightRight = (TreeNode *) malloc(sizeof(TreeNode));

	TreeNode *rootLeftLeftRight = (TreeNode *) malloc(sizeof(TreeNode));

	tree = root;
	tree->data = 'A';
	tree->parent = nullptr;
	tree->leftChild = rootLeft;
	tree->rightChild = rootRight;
	tree->leftTag = 0;
	tree->rightTag = 0;

	rootLeft->data = 'B';
	rootLeft->parent = tree;
	rootLeft->leftChild = rootLeftLeft;
	rootLeft->rightChild = rootLeftRight;
	rootLeft->leftTag = 0;
	rootLeft->rightTag = 0;

	rootRight->data = 'C';
	rootRight->parent = tree;
	rootRight->leftChild = rootRightRight;
	rootRight->rightChild = nullptr;
	rootRight->leftTag = 0;
	rootRight->rightTag = 0;

	rootLeftLeft->data = 'D';
	rootLeftLeft->parent = rootLeft;
	rootLeftLeft->leftChild = nullptr;
	rootLeftLeft->rightChild = rootLeftLeftRight;
	rootLeftLeft->leftTag = 0;
	rootLeftLeft->rightTag = 0;

	rootLeftRight->data = 'E';
	rootLeftRight->parent = rootLeft;
	rootLeftRight->leftChild = nullptr;
	rootLeftRight->rightChild = nullptr;
	rootLeftRight->leftTag = 0;
	rootLeftRight->rightTag = 0;

	rootRightRight->data = 'F';
	rootRightRight->parent = rootRight;
	rootRightRight->leftChild = nullptr;
	rootRightRight->rightChild = nullptr;
	rootRightRight->leftTag = 0;
	rootRightRight->rightTag = 0;

	rootLeftLeftRight->data = 'G';
	rootLeftLeftRight->parent = rootLeftLeft;
	rootLeftLeftRight->leftChild = nullptr;
	rootLeftLeftRight->rightChild = nullptr;
	rootLeftLeftRight->leftTag = 0;
	rootLeftLeftRight->rightTag = 0;
}


TreeNode *prefix;
/**
 * 访问各个节点
 * @param treeNode 树
 */
void visit(TreeNode *treeNode) {
	// 左线索
	if (treeNode->leftChild == nullptr) {
		treeNode->leftChild = prefix;
		treeNode->leftTag = 1;
	}

	// 右线索
	if (prefix != nullptr && prefix->rightChild == nullptr) {
		prefix->rightChild = treeNode;
		prefix->rightTag = 1;
	}
	prefix = treeNode;
}

/**
 * 先序遍历 根->左->右
 * @param tree 树
 */
void first(Tree tree) {
	if(tree->rightChild == nullptr && tree->rightTag == 0) {
		return;
	}
	visit(tree);
	if (tree->leftTag == 0) {
		first(tree->leftChild);
	}
	first(tree->rightChild);
}

void firstPrint(Tree tree) {
	if(tree == nullptr) {
		return;
	}
	printf("%c->", tree->data);
	if (tree->leftTag == 0) {
		firstPrint(tree->leftChild);
	}
	firstPrint(tree->rightChild);
}


/**
 * 创建线索二叉树
 * @param tree
 */
void firstCreate(Tree tree) {
	// 前缀
	prefix = nullptr;
	if (tree != nullptr) {
		first(tree);
		if (prefix->rightChild == nullptr) {
		    prefix->rightTag = 1;
		}
	}
	firstPrint(tree);
}

void inOrderPrint(Tree tree) {
	if(tree == nullptr) {
		return;
	}
	inOrderPrint(tree->leftChild);
	visit(tree);
	printf("%c->", tree->data);
	inOrderPrint(tree->rightChild);
}

void postOrderPrint(Tree tree) {
	if(tree == nullptr) {
		return;
	}
	postOrderPrint(tree->leftChild);
	postOrderPrint(tree->rightChild);
	visit(tree);
	printf("%c->", tree->data);
}

Tree init() {
	return nullptr;
}